1. Field of the Invention
The present invention relates to a storage device, and more particularly to a storage device which is preferably used for hierarchical encoding and storing of image data.
2. Description of the Related Art
There is a method for encoding high-resolution image data called "hierarchical encoding", wherein high-resolution image data is used as image data of the lowest hierarchy or first hierarchy and image data of a second hierarchy with fewer pixels than the image data of the first hierarchy is formed, image data of a third hierarchy with fewer pixels than the image data of the second hierarchy is formed, and so on until image data is formed to the highest hierarchy. The image data for each hierarchy is displayed on a monitor with resolution or number of pixels corresponding to that hierarchy. The user is able to select the hierarchically encoded image data corresponding with his/her monitor, and thus view corresponding contents.
However, considering an arrangement in which image data of a certain resolution is used as the image data for the lowest hierarchy or first hierarchy, image data of higher hierarchies is sequentially formed and the hierarchically encoded image data is stored or transferred, extra storage capacity or transferring capacity becomes necessary as compared to arrangements in which only the image data of the lowest hierarchy is stored or sent, because of the increased data of the upper hierarchies.
Accordingly, the present Applicant has in the past proposed a hierarchical encoding method in which there is no increase in storage capacity or the like.
For example, let us consider an arrangement in which the average value of 4 pixels formed of 2 by 2 pixels on the lowest hierarchy is used as the image value of the upper hierarchy, whereby 3-tier hierarchical encoding is performed. As shown in FIG. 1A, the average value m0 of the 4 pixels h00, h01, h02, and h03, these being the 2 by 2 pixels to the upper left of the 8 by 8 pixels, this m0 comprising 1 pixel to the upper left in the second hierarchy. In the same manner, the average value m1 of the 4 pixels h10, h11, h12, and h13 to the upper right of the image of the lowest hierarchy, the average value m2 of the 4 pixels h20, h21, h22, and h23 to the lower left thereof, and the average value m3 of the 4 pixels h30, h31, h32, and h33 to the lower right thereof, are calculated, these each comprising 1 pixel to the upper right, lower left, and lower right of the second hierarchy. Further, the average value q of the 4 pixels m0, m1, m2, and m3, these being the 2 by 2 pixels comprising the second hierarchy, is calculated, this average value q being used as the pixel of the image of the highest hierarchy.
In order to store or transfer all the pixels h00 through h03, h10 through h13, h20 through h23, h30 through h33, m0 through m3, and q, in that form without any change, storage capacity equal to m0 through m3 and q becomes necessary.
As shown in FIG. 1B, let us say that the pixel q of the third hierarchy is placed in the position of the lower right pixel m3 of the pixels m0 through m3 in the second hierarchy. The second hierarchy is thus comprised of the pixels m0 through m2 and q.
As shown in FIG. 1C, let us say that the pixel m0 of the second hierarchy is placed in the position of the lower right pixel h03 of the pixels h00 through h03 in the third hierarchy used to obtain the pixel m0. The remaining pixels of the second hierarchy, m1 through m2 and q are also positioned in the place of the pixels h13, h23, and h33 of the first hierarchy. The pixel q has not been directly obtained from pixel h30 through h33, but exists on the second hierarchy instead of the pixel m3 which has been directly obtained from the pixels h30 through h33, and so pixel q is positioned on the place of the pixel h33, instead of pixel m3.
As shown in FIG. 1C, the entire number of pixels is 4 by 4 pixels totaling 16 pixels, which is unchanged from the number of pixels of the lowest hierarchy as shown in FIG. 1A. Thus, increase in required storage capacity and the like can be prevented.
Decoding of the pixel m3 which has been replaced with pixel q and of the pixels h03, h13, h23, and h33 which have been respectively replaced with pixels m0 through m3 is performed as follows.
q is the average value of m0 through m3, so the expression q=(m0+m1+m2+m3)/4 holds. Hence, m3 can be obtained by the expression m3=4.times.q-(m0+m1+m2).
Also, m0 is the average value of h00 through h03, so the expression m0=(h00+h01+h02+h03)/4 holds. Hence, h03 can be obtained by the expression h03=4.times.m0-(h00+h01+h02). Also, h13, h23, and h33 can be obtained in the same way.
Known arrangements for performing such hierarchical encoding have involved general-use memory such as SRAM (Static Random Access Memory) or DRAM (Dynamic RAM) for storing the hierarchical encoding results being provided externally with an adder for calculating the average values, a shifter, a delay circuit for line delay, and so forth.
In the case shown in FIG. 1C, in order to obtain the pixel m0 of the second hierarchy, the expression m0=(h00+h01+h02+h03)/4 must be calculated. To that end, an adder for adding the values in the parenthesis, and a shifter for dividing the addition results by 4, i.e., to shift 2 bits to the right, are needed.
Further, in order to obtain the pixel m0 of the second hierarchy, the pixels h00 through h03 which exist over two lines in the first hierarchy become necessary. Supplying of image data to the memory is generally performed in the order of raster scanning. Reading and writing of the image data to the memory is also performed in the order of raster scanning, i.e., one line at a time.
The line that begins with h00 is delayed one line worth in the delay circuit, waits for the line beginning with h02 to be supplied, then calculates m0, following which the line beginning with h00 and the line beginning with h02 are written to the memory.
In this way, known arrangements required that various types of circuits be provided externally to the memory, increasing the size of the device. There has also been the problem in that the various types of circuits provided externally to the memory restricted the processing speed of the overall device.